import java.util.LinkedList;

public class LeetCode331 {
        /**
         * 验证给定的字符串是否为有效的二叉树前序序列化。
         *
         * @param preorder 二叉树的前序序列化字符串，节点间以逗号分隔。
         * @return 如果给定字符串是有效的前序序列化，则返回true；否则返回false。
         */
        public boolean isValidSerialization(String preorder) {
            // 将输入字符串按照逗号分割成节点数组
            String[] nodes = preorder.split(",");

            // 初始化槽位计数器，根节点需要一个槽位
            int slot = 1;

            // 遍历所有节点
            for (String node : nodes) {
                // 如果当前没有可用的槽位，但还有未处理的节点，则说明序列化无效
                if (slot == 0) {
                    return false;
                }

                // 处理空节点（#），消耗一个槽位
                if (node.equals("#")) {
                    slot--;
                } else {
                    // 处理非空节点，消耗一个槽位，并为左右子节点各增加一个槽位
                    // 因此净增加的槽位数为 +2 -1 = +1
                    slot++;
                }
            }

            // 最终所有槽位都应被恰好消耗完
            return slot == 0;
        }
}
